package org.unt.tree.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Tree {

	public static void main(String[] args) {
		Tree tree = buildSample();
		String item = tree.getFirstNoFatherAndRemove();
		System.out.println(item);
		while (!item.equals("root")) {
			item = tree.getFirstNoFatherAndRemove();
			System.out.println(item);
		}
		tree.printStatus();
	}

	static Tree buildSample() {
		Tree tree = new Tree();
		tree.addChild("root", "C");
		tree.addChild("C", "A");
		tree.addChild("C", "B");
		tree.addChild("B", "D");
		tree.addChild("root", "E");
		return tree;
	}

	private Map<String, Node> map;

	private Node rootN;

	public Tree() {
		rootN = new Node("root", new ArrayList());
		map = new HashMap<String, Node>();
		map.put("root", rootN);
	}

	public void printStatus() {
		System.out.println("root children amount " + rootN.getChildren().size());
		System.out.println("map key set amount " + map.keySet().size());
	}

	public boolean exists(String name) {
		return map.containsKey(name);
	}

	public void addChild(String father, String son) {

		if (map.get(son) != null) {
			return;
		}

		Node fatherN = map.get(father);
		if (fatherN == null) {
			throw new RuntimeException("Father '" + father + "' do not exist");
		}

		Node sonN = new Node(son, new ArrayList<Node>());
		fatherN.getChildren().add(sonN);
		map.put(son, sonN);
	}

	public String getFirstNoFatherAndRemove() {

		Node father = null;

		Node node = rootN;
		List<Node> children = rootN.getChildren();

		while (children.size() > 0) {

			father = node;
			node = children.get(0);
			children = node.getChildren();
		}

		String name = node.getName();
		if (father != null) {
			father.getChildren().remove(0);
		}
		map.remove(name);

		return name;
	}

	public void removeChild(String noFather) {
		// map.get(noFather);
	}

	public Node getNode(String item) {
		return map.get(item);
	}
}
